/**
 * @a https://leetcode.cn/problems/decode-string/
 */

#include "common.h"

class Solution {
public:
    string decodeString(string s) {
        stack<string> strs;
        stack<int> nums;
        
        strs.push("");
        int i = 0, sz = s.size();
        while(i < sz){
            if(s[i] >= '0' && s[i] <= '9'){
                int tmp = 0;
                while(s[i] >= '0' && s[i] <= '9'){
                    tmp = tmp * 10 + (s[i] - '0');
                    ++i;
                }
                nums.push(tmp);
            }
            else if(s[i] == '['){
                ++i;        //skip '['
                int pos = i;
                while(s[i] >= 'a' && s[i] <= 'z') ++i;

                string str = s.substr(pos, i - pos);
                strs.push(str);
            }
            else if(s[i] == ']'){
                string top = strs.top();
                strs.pop();
                int n = nums.top();
                nums.pop();

                while(n--) strs.top() += top;
                ++i;
            }
            else            //normal char
            {
                while(i < sz && s[i] >= 'a' && s[i] <= 'z')
                {
                    strs.top() += s[i];
                    ++i;
                }
            }
        }
        return strs.top();
    }
};





// class Solution
// {
// public:
//     string decodeString(string s)
//     {
//         return decodeString_aux(s);
//     }

// private:
//     string decodeString_aux(const string &s)
//     {
//         if (s.empty())
//             return "";

//         int pos_lsqr = s.find_first_of('[');
//         if (pos_lsqr == std::string::npos)
//             return s;

//         int pos_rsqr = s.find_first_of(']');
//         if (pos_rsqr = std::string::npos)
//             ; // 异常处理,算法题不可能

//         // num[ xxxx ]
//         string l_str = s.substr(pos_lsqr + 1, s.find_first_of('['));
//         string substring = s.substr(pos_lsqr + 1, pos_rsqr - pos_lsqr - 1);

//         string ret = decodeString_aux(substring);

//         int num = stoi(s.substr(0, pos_lsqr));
//         if (num == 0)
//             return "";
        
//         while (num--)
//         {
//             ret += substring;
//         }
//         return ret;
//     }
// };